package P2分治回溯;

public class Recursion {
    public static void main(String[] args) {
        //show();
        //show(5);
        //return;

        //1~n求和 迭代
        System.out.println(nSum(100));
        System.out.println(nSumRecursion(100));

        //斐波那契数列 迭代
        System.out.println(fibo(44));
        System.out.println(fiboRecursion(44));
    }

    //O(2^N)
    private static int fiboRecursion(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fiboRecursion(n - 1) + fiboRecursion(n - 2);
    }
    //O(N)
    private static int nSumRecursion(int n) {
        if (n == 1) {
            return 1;
        }
        return nSumRecursion(n - 1) + n;
    }
    //O(N)
    private static int fibo(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        /*
        1 1 2 3 5 8 13 21 34 55
        0 1 2 3 4 5 6  7  8  9
                             i
        */
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n - 1];
    }


    //O(N)
    private static int nSum(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }

    public static void show(int n) {
        System.out.println(n);
        if (n == 1) {
            return;
        }
        show(n - 1);
        //return;
    }
    //Stack Overflow Error 栈内存溢出
    public static void show() {
        System.out.println("show...");
        show();
    }
}
